#include<vector>
#include<algorithm>
using namespace std;
class Solution {
private:
    int check(const vector<int>& arr, int x) {
        int ret = 0;
        for (const int& num : arr) {
            ret += (num >= x ? x : num);
        }
        return ret;
    }
public:
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        vector<int>prefix(arr.size() + 1);
        for (int i = 1; i <= arr.size(); ++i)
            prefix[i] = arr[i - 1] + prefix[i - 1];
        int left = 0, right = arr.back();
        int index = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            auto iter = lower_bound(arr.begin(),arr.end(), mid);
            int index = iter - arr.begin();
            int tmp = prefix[index] + (arr.size() - index) * mid;
            if (tmp<target) 
                left = mid + 1;
            else 
                right = mid - 1;
        }
        int choose_small = check(arr, right);
        int choose_big = check(arr, left);
        return abs(choose_small - target) <= abs(choose_big - target) ? right : left;
    }
};


int main() {
    Solution sol;
    vector<int> arr = { 4,9,3};
    auto res=sol.findBestValue(arr,10);
    ++res;
}